package cn.hughie.sort;

import utils.SortUtils;

import java.util.regex.Pattern;

/**
 * 堆排序
 *
 * @author yuh
 * @date 2018/5/16 19:39
 */
public class HeapSort {

    public static void heapSort(Comparable[] arr) {
        int length = arr.length;
        for (int i = (length - 1) / 2; i >= 0; i--) {
            sink(arr, i, length - 1);
        }

        for (int i = length - 1; i > 0; ) {
            SortUtils.swap(arr, i--, 0);
            sink(arr, 0, i);
        }
    }

    private static void sink(Comparable[] arr, int k, int l) {
        while (2 * k + 1 <= l) {
            int c = 2 * k + 1;
            if (c + 1 <= l && SortUtils.largerThan(arr[c+1], arr[c])) {
                c++;
            }
            if (!SortUtils.largerThan(arr[c], arr[k])) {
                break;
            }
            SortUtils.swap(arr, k, c);
            sink(arr, c, l);
        }

    }

    public static void main(String[] args) {
        Integer[] arr = {2, 3, 4, 1, 3, 4, 52, 44, 41, 41, 41, 41, 4, 14, 141, 41, 14, 1, 41, 41, 4, 14};
        heapSort(arr);
        SortUtils.isSorted(arr);
    }
}
